package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.7 MB, 在所有 Go 提交中击败了71.85%的用户
 */
var ans []string

func generateParenthesis(n int) []string {

	ans = []string{}
	dfs(n, 0, 0, "")
	return ans
}

func dfs(n int, lc int, rc int, seq string) {
	if lc == n && rc == n {
		ans = append(ans, seq)
	} else {
		if lc < n { dfs(n, lc + 1, rc, seq + "(") }
		if rc < n && rc < lc { dfs(n, lc, rc + 1, seq + ")") }
	}
}

func main() {

	fmt.Println(generateParenthesis(3))
}
